package 每日一题;

import common.GeneralFunction;

import java.util.ArrayList;
import java.util.List;

public class No43字符串相乘 {

    /**
     * 给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
     *
     * 示例 1:
     * 输入: num1 = "2", num2 = "3"
     * 输出: "6"
     * 示例 2:
     * 输入: num1 = "123", num2 = "456"
     * 输出: "56088"
     *
     * 说明：
     * num1 和 num2 的长度小于110。
     * num1 和 num2 只包含数字 0-9。
     * num1 和 num2 均不以零开头，除非是数字 0 本身。
     * 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。
     */

    //mn+n^2,复杂度较高。  O(mn)优化版在下面
    public String multiply(String num1, String num2) {

        if("0".equals(num1)||"0".equals(num2)){
            return "0";
        }

        num1=new StringBuilder(num1).reverse().toString();
        num2=new StringBuilder(num2).reverse().toString();
        char[] cArr1 = num1.toCharArray();
        char[] cArr2 = num2.toCharArray();

        List<String> list=new ArrayList<>();
        int carryNum=0;

        for (int i = 0; i < cArr1.length; i++) {

            StringBuilder sb=new StringBuilder();
            int number1=cArr1[i]-'0';
            //提前先加好0
            for (int j = 0; j < i; j++) {
                sb.append("0");
            }

            for (int j = 0; j < cArr2.length; j++) {

                int number2=cArr2[j]-'0';
                int sum=(number1*number2)+carryNum;
                int thisNum=sum%10;
                carryNum=sum/10;
                sb.append(thisNum);

            }

            if(carryNum!=0){
                sb.append(carryNum);
                carryNum=0;
            }

            list.add(sb.reverse().toString());
        }

        String result="0";

        for (String str : list) {
            result=addStrings(result,str);
        }

        return result;
    }

    @SuppressWarnings("all")
    private String addStrings(String num1, String num2) {
        //竖着相加

        num1=new StringBuilder(num1).reverse().toString();
        num2=new StringBuilder(num2).reverse().toString();
        char[] cArr1 = num1.toCharArray();
        char[] cArr2 = num2.toCharArray();
        int minLength=Math.min(cArr1.length,cArr2.length);

        StringBuilder sb=new StringBuilder();
        int carryNum=0;

        for (int i = 0; i < minLength; i++) {
            int number1=cArr1[i]-'0';
            int number2=cArr2[i]-'0';

            int sum=number1+number2+carryNum;
            int thisNum=sum%10;
            carryNum=sum/10;
            sb.append(thisNum);
        }

        if(cArr1.length>minLength){
            for (int i = minLength; i < cArr1.length; i++) {
                int sum=cArr1[i]-'0'+carryNum;
                int thisNum=sum%10;
                carryNum=sum/10;
                sb.append(thisNum);
            }
        }else if(cArr2.length>minLength){
            for (int i = minLength; i < cArr2.length; i++) {
                int sum=cArr2[i]-'0'+carryNum;
                int thisNum=sum%10;
                carryNum=sum/10;
                sb.append(thisNum);
            }
        }
        if(carryNum!=0){
            sb.append(carryNum);
        }

        return sb.reverse().toString();
    }

    //O(mn)优化版  用数组装原数,最后再进行打理
    public String multiplyGood(String num1,String num2) {

        if("0".equals(num1)||"0".equals(num2)){
            return "0";
        }

        num1=new StringBuilder(num1).reverse().toString();
        num2=new StringBuilder(num2).reverse().toString();
        char[] cArr1 = num1.toCharArray();
        char[] cArr2 = num2.toCharArray();

        int[] product=new int[Math.max(cArr1.length,cArr2.length)*2];

        int maxLength=0;

        for (int i = 0; i < cArr1.length; i++) {

            int number1=cArr1[i]-'0';

            for (int j = 0; j < cArr2.length; j++) {

                int number2=cArr2[j]-'0';
                //不处理溢出10,后续处理
                product[i+j]+=number1*number2;
                maxLength=Math.max(maxLength,i+j);
            }

        }

        StringBuilder sb=new StringBuilder();
        int carryNum=0;
        //开始转换数组,处理溢出问题
        for (int i = 0; i < maxLength+1; i++) {
            int sum=product[i]+carryNum;
            int thisNum=sum%10;
            carryNum=sum/10;
            sb.append(thisNum);
        }

        if(carryNum!=0){
            sb.append(carryNum);
        }

        if(sb.lastIndexOf("0")==sb.length()-1){
            sb.substring(0,sb.length()-1);
        }

        return sb.reverse().toString();
    }

    public static void main(String[] args) {
        GeneralFunction generalFunction=new GeneralFunction(No43字符串相乘.class,"9", "9");
        generalFunction.runAllMethod();
    }

}
